<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      // 同类型题目
      // 121
      var maxProfit = function (prices) {
        // 方法一：暴力法（）---时间O（n）（）---空间：O（1）（）
        // let sum = 0;
        // for (let i = 0; i < prices.length; i++) {
        //   if (prices[i] > prices[i - 1]) {
        //     sum += prices[i] - prices[i - 1];
        //   }
        // }
        // return sum;

        // 方法一：动态规划：（）---时间：O（n）（）---空间：O（2n=>n）（二维数组）
        // 状态转移方程
        // bass case
        // dp[-1][...][0] = dp[...][0][0] = 0
        // dp[-1][...][1] = dp[...][0][1] = -infinity
        // 今天没有持有股票---昨天休息---今天卖出
        // dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
        // 今天持有股票---昨天持有---今天买入
        // dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
        const length = prices.length;
        const dp = Array(length)
          .fill(0)
          .map(() => Array(2).fill(0));
        for (let i = 0; i < prices.length; i++) {
          if (i - 1 < 0) {
            //   dp[i][0]
            // = max(dp[-1][0], dp[-1][1] + prices[i])
            // = max(0, -infinity + prices[i]) = 0
            dp[i][0] = 0;
            //   dp[i][1]
            // = max(dp[-1][1], dp[-1][0] - prices[i])
            // = max(-infinity, 0 - prices[i])
            // = -prices[i]
            dp[i][1] = -prices[i];
            continue;
          }
          dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
          dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[length - 1][0];

        // 方法二：动态规划：（优化空间复杂度）---时间：O（n）（）---空间：O（1）（）
        // const length = prices.length;
        // let dp_i_0 = 0;
        // let dp_i_1 = 0;
        // for (let i = 0; i < prices.length; i++) {
        //   if (i - 1 < 0) {
        //     dp_i_0 = 0;
        //     dp_i_1 = -prices[i];
        //     continue;
        //   }
        //   dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        //   dp_i_1 = Math.max(dp_i_1, dp_i_0 - prices[i]);
        // }
        // return dp_i_0;
      };

      console.log(maxProfit([7, 1, 5, 3, 6, 4]));
    </script>
  </body>
</html>
